package easy

import (
	. "GoLeetcode/common"
)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

// 二叉搜索树,如果root.Val <low则说明应该遍历右子树
// root.Val > high 则说明应该遍历左子树
func rangeSumBST(root *TreeNode, low int, high int) int {
	if root == nil {
		return 0
	}
	if root.Val < low {
		return rangeSumBST(root.Right, low, high)
	}
	if root.Val > high {
		return rangeSumBST(root.Left, low, high)
	}
	return root.Val + rangeSumBST(root.Left, low, high) + rangeSumBST(root.Right, low, high)
}

func rangeSumBST1(root *TreeNode, low int, high int) int {
	if root == nil {
		return 0
	}
	result := 0
	if root.Val >= low && root.Val <= high {
		result += root.Val
	}
	return result + rangeSumBST(root.Left, low, high) + rangeSumBST(root.Right, low, high)
}
